#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct
{
	unsigned char lcheck :8;
	unsigned char leaf :1;
	unsigned char split :1;
	unsigned int base :22;
} tBc;

typedef struct
{
	tBc* bc;
	char* tail;
} tDatrie;

char* alphabet = "#ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz";
const int LCHECK_MASK = 0xFF000000;
const int LEAF_MASK = 0x00800000;
const int SPLIT_MASK = 0x00400000;
const int BASE_MASK = 0x003FFFFF;

void convertEndianness(int* bc, int size)
{
	int i;
	char* cp;
	for (i = 0; i < size / sizeof(int); i++)
	{
		cp = (char*) (bc + i);
		char tmp = cp[0];
		cp[0] = cp[3];
		cp[3] = tmp;
		tmp = cp[1];
		cp[1] = cp[2];
		cp[2] = tmp;
	}
}

char getLcheck(tBc bc)
{
	int intBc = *(int*) &bc;
	return (intBc & LCHECK_MASK) >> 24;
}

int getBase(tBc bc)
{
	int intBc = *(int*) &bc;
	return intBc & BASE_MASK;
}

int isLeaf(tBc bc)
{
	int intBc = *(int*) &bc;
	return !!(intBc & LEAF_MASK);
}

int getSplit(tBc bc)
{
	int intBc = *(int*) &bc;
	return !!(intBc & SPLIT_MASK);
}

int compare(tDatrie datrie, int index, char* sfx)
{
	int pos = getBase(datrie.bc[index]);
	int len = strlen(sfx) + 1;
	char* comparable;
	int i = 0, j;
	int returnVal;
	char sizeSuffix1;
	if (getSplit(datrie.bc[index]))
	{
		comparable = malloc(len * sizeof(char));
		for (j = 0; j < len; j++)
			comparable[j] = 0;
		while (datrie.tail[pos + i] != '#' && i < len) // Leyendo prefix
		{
			comparable[i] = datrie.tail[pos + i];
			i++;
		}
		sizeSuffix1 = datrie.tail[pos + i + 1];
		if (sizeSuffix1 + strlen(comparable) > len - 1)
			returnVal = 0;
		else
		{
			strncat(comparable + i, datrie.tail + pos + i + 2, sizeSuffix1);
			if (!strncmp(sfx, comparable, strlen(sfx))) // Si sfx es igual al prefijo + el primer sufijo
				returnVal = 1;
			else
			{
				for (j = i; j < len; j++)
					comparable[j] = 0;
				while (datrie.tail[pos + i + sizeSuffix1 + 1] != '#' && i < len) // Construyendo el segundo sufijo
				{
					comparable[i] = datrie.tail[pos + i + sizeSuffix1 + 2];
					i++;
				}
				if (!strncmp(sfx, comparable, strlen(sfx))) // Si sfx es igual al prefijo + el segundo sufijo
					returnVal = 1;
				else
					returnVal = 0;
			}
		}
		free(comparable);
		return returnVal;
	}
	else if (!isLeaf(datrie.bc[index]) && getLcheck(datrie.bc[pos]) == '#')
		return strlen(sfx) == 0;
	else if (!strncmp(sfx, datrie.tail + pos, strlen(sfx)))
		if (pos > strlen(datrie.tail))
			return 0;
		else
			return datrie.tail[pos + strlen(sfx)] == '#';
	else
		return 0;
}

int lgoto(tDatrie datrie, int src, char c)
{
	int dest = (strchr(alphabet, c) - alphabet) + getBase(datrie.bc[src]);
	if (getLcheck(datrie.bc[dest]) == c)
		return dest;
	return 0;
}

/**
 * Devuelve 1 si encuentra a s en el trie datrie, 0 si no
 */
int mretrieval(tDatrie datrie, char* str)
{
	int i = 0;
	int index = 0; // root
	while ((!isLeaf(datrie.bc[index])) && str[i])
	{
		index = lgoto(datrie, index, str[i]);
		if (index == 0)
			return 0;
		i++;
	}
	return compare(datrie, index, str + i);
}

int main(int argc, char*argv[])
{
	FILE *fBc, *fTail, *fSearch;
	int bcSize, tailSize;
	char buscable[100];
	int i;

	if (!(fBc = fopen("bc.dat", "rb")))
	{
		perror("No pude abrir bc.dat");
		return -1;
	}

	if (!(fTail = fopen("tail.dat", "rb")))
	{
		perror("No pude abrir tail.dat");
		return -2;
	}

	if (!(fSearch = fopen("palabras.txt", "rt")))
	{
		perror("No pude abrir palabras.txt");
		return -3;
	}

	fseek(fBc, 0L, SEEK_END);
	bcSize = ftell(fBc);
	fseek(fBc, 0L, SEEK_SET);
	fseek(fTail, 0L, SEEK_END);
	tailSize = ftell(fTail);
	fseek(fTail, 0L, SEEK_SET);

	tDatrie datrie;
	datrie.bc = malloc(bcSize);
	datrie.tail = malloc(tailSize);
	fread(datrie.bc, bcSize, 1, fBc);
	fread(datrie.tail, tailSize, 1, fTail);
	convertEndianness((int*) datrie.bc, bcSize);

	time_t start = time(NULL);
	for (i = 0; i < 100; i++)
	{
		fseek(fSearch, 0L, SEEK_SET);
		while (fgets(buscable, 100, fSearch))
		{
			char* newLinePos = strchr(buscable, '\n');
			if (newLinePos)
				*newLinePos = '\0';
			printf("Buscando palabra: %s. ", buscable);
			printf(mretrieval(datrie, buscable) ? "Success\n" : "Failure\n");
		}
	}
	time_t stop = time(NULL);

	printf("Tiempo transcurrido: %f segundos", difftime(stop, start));

	fclose(fBc);
	fclose(fTail);
	fclose(fSearch);
	free(datrie.bc);
	free(datrie.tail);

	return 0;
}
